package 哈希表;

import java.util.Scanner;

//散列表又称哈希表

/**
 * 1. 结点
 * 2. 单链表
 * 3. 哈希表
 * @author PC
 *
 */
public class 哈希表 {
	public static void main(String[] args) {
		//创建哈希表
		HashTab hashTab = new HashTab(7);
		
		String key = "";
		Scanner sc = new Scanner(System.in);
		while(true) {
			System.out.println("add 添加员工");
			System.out.println("find 查找员工");
			System.out.println("list 遍历员工");
			System.out.println("exit 退出系统");
			key = sc.next();
			switch (key) {
			case "add":
				System.out.println("输入id:");
				int id = sc.nextInt();
				System.out.println("输入name:");
				String name = sc.next();
				Emp emp = new Emp(id, name);
				hashTab.add(emp);
				break;
			case "find":
				System.out.println("输入要查找id:");
				id = sc.nextInt();
				hashTab.findEmpById(id);
				break;
			case "list":
				hashTab.list();
				break;
			case "exit":
				sc.close();
				System.exit(0);
				break;
			default:
				break;
			}
		}
	}
}

/**
 *  哈希表,散列表,用来处理将键值放到哪个地址中,其中有增删查方法
 * @author PC
 *
 */
class HashTab{
	//哈希表长,代表有几个单链表
	private int size;
	//哈希表,里面放链表
	private EmpLinkedList[] empLinkedListArray;
	
	//构造器
	public HashTab() {
		super();
	}
	public HashTab(int size) {
		this.size = size;
		//初始化empLinkedListArray
		empLinkedListArray = new EmpLinkedList[size];
		//empLinkedListArray代表哈希表,其中每一个地址表示一个单链表,单链表也需要初始化
		for(int i = 0; i < size; i++) {
			empLinkedListArray[i] = new EmpLinkedList();
		}
	}
	
	/**
	 * 散列函数,除留取余法,求出散列地址
	 * @param id
	 * @return
	 */
	public int hash(int id) {
		return id % size;
	}
	
	/**
	 * 添加员工结点,选择添加到那个地址中
	 * @param emp
	 */
	public void add(Emp emp) {
		//使用散列函数的到地址
		int empLinkedListNO = hash(emp.id);
		//将emp添加到对应链表
		empLinkedListArray[empLinkedListNO].add(emp);
	}
	
	/**
	 * 根据id查找员工结点,也需要利用散列函数找到这个结点地址
	 * @param id
	 * @return
	 */
	public void findEmpById(int id) {
		//使用散列函数找到地址,就是在那个链表中
		int empLinkedListNO = hash(id);
		Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
		if(emp != null) {
			//找到
			System.out.println("在"+(empLinkedListNO+1)+"条链表中,找到员工id="+id);
		}else {
			//没找到
			System.out.println("未找到"+id+"员工");
		}
	}
	
	/**
	 * 遍历
	 */
	public void list() {
		for(int i = 0 ; i < size ; i++) {
			empLinkedListArray[i].list(i);
		}
	}
	
}


/**
 *  链表
 * @author PC
 *
 */
class EmpLinkedList{
	
	//声明头结点,直接将第一个添加到头结点位置,没有初始化链表,直接插入
	private Emp head;
	
	/**
	 * 添加员工
	 * @param emp
	 */
	public void add(Emp emp) {
		//如果是第一个员工
		if(head == null) {
			head = emp;
			return;
		}
		//如果不是第一个,使用辅助指针移动到最后
		Emp curEmp = head;
		while(true) {
			if(curEmp.next == null) {
				break;
			}
			//后移
			curEmp = curEmp.next;
		}
		curEmp.next = emp;
	}
	
	/**
	 * 查找员工
	 * @param id
	 * @return
	 */
	public Emp findEmpById(int id) {
		//判空
		if(head == null) {
			System.out.println("链表空...");
			return null;
		}
		//辅助指针
		Emp curEmp = head;
		while(true) {
			if(curEmp.id == id) {
				//找到
				break;
			}
			
			if(curEmp.next == null) {
				//找到最后没找到,反空
				curEmp = null;
				break;
			}
			//循环下一个
			curEmp = curEmp.next;
		}
		return curEmp;
	}
	
	/**
	 * no 标记第几个链表,是哈希表传过来的参数
	 * @param no
	 */
	public void list(int no) {
		//判空
		if(head == null) {
			System.out.println("链表空...");
			return;
		}
		System.out.print("第"+(no+1)+"个链表");
		//辅助指针
		Emp curEmp = head;
		while(true) {
			System.out.print("->"+curEmp.id+"-"+curEmp.name);
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;
		}
		System.out.println();
	}
}

/**
 *  结点
 * @author PC
 *
 */
class Emp{
	public int id;
	public String name;
	//指针域
	public Emp next;
	
	//构造器，不需要next
	public Emp() {
		super();
	}
	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
	//toString不需要next
	@Override
	public String toString() {
		return "Emp [id=" + id + ", name=" + name + "]";
	}
}